package com.michael.demos.base.java.sort;

import com.michael.demos.base.java.utils.TreePrinter;

/**
 * 类功能描述:
 * <pre>
 *   堆排序示例
 * </pre>
 *
 * @author Michael
 * @version 1.0
 * @date 2020/9/15 14:11
 */
public class HeapSortDemo {

    public static void main(String[] args) {
        int[] arr = new int[]{8, 9, 7, 6, 5, 2, 1, 3, 4, 10, 11};
        //开始位置时最后一个非叶子节点，即最后一个节点的父节点
        //调整为大顶堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            maxHeapAdjust(arr, i, arr.length);
        }
        System.out.println("\n已经生成大顶堆,如下图");
        TreePrinter.show(arr);

        // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            // 将堆顶记录和当前未经排序子序列的最后一个记录交换
            doSwap(arr, 0, i);
            // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
            maxHeapAdjust(arr, 0, i);
        }

        // 排序完成
        System.out.println("排序完成：");
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k]);
            if (k < arr.length - 1) {
                System.out.print("\t");
            }
        }
        System.out.println();
    }

    /**
     * 数组中的某一段调整为大堆
     *
     * @param arr     需要转换成大堆的数组
     * @param index   需要调整的堆根节点的序号
     * @param maxSize 需要调整的堆的最大序号
     */
    public static void maxHeapAdjust(int[] arr, int index, int maxSize) {

        int leftIndex = (index << 1) + 1;
        int rightIndex = (index << 1) + 2;
        int maxIndex = index;

        if (leftIndex < maxSize && arr[leftIndex] > arr[maxIndex]) {
            maxIndex = leftIndex;
        }

        if (rightIndex < maxSize && arr[rightIndex] > arr[maxIndex]) {
            maxIndex = rightIndex;
        }

        // 需要调整才调整
        if (maxIndex != index) {
            doSwap(arr, index, maxIndex);
            // 递归调整子树
            maxHeapAdjust(arr, maxIndex, maxSize);
        }
    }

    /** 交换数组中元素位置 */
    public static void doSwap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}
